1. Field of Invention
The present invention relates to image processing. More particularly, the present invention relates to a method for performing a motion estimation combined with a Walsh-Hadamard transform (WHT), so as to at least reduce the computation load and increase the operation speed.
2. Description of Related Art
As the fabrication technology have been greatly improved, the displaying device now has allowed a displaying manner in digital format, such as the liquid crystal display (LCD) panel or HDTV. The image is composed of a large number of image pixels. Each of the image pixels can be separately controlled. However, the image usually is displayed in motion, then the image processing is necessary to transform each of the pixels.
Motion estimation (ME) and discrete cosine transformation (DCT)-coding have been developed and adopted to eliminate the temporal redundancy in image sequences by most video encoding algorithms, such as MPEG 1, MPEG 2, H.261, H.263, and so on. In this motion estimation algorithm, the sum of absolute difference (SAD) of the luminance pixels has been widely used as matching criterion in ME. It generates a different block with minimum energy, but there might be large special redundancies and it requires more encoding bit-amounts.
The algorithm for the conventional motion estimation is shown in FIG. 1. In FIG. 1, the image frame 100 within, for example, a 3 by 3 block with 9 elements is shown. The image object 102a is moved to the image object 102b. For example, the central element all has been shifted to a lower-right new location. Then, these two elements with respect to the concerning element all are taken out and subtracted to each other by the subtractor 104. And then, the parameters for the motion vector (MV) are determined. The quantity of the sum of absolute difference (SAD) of luminance pixels is used as the matching criterion, where
                                          SAD            ⁡                          (                              i                ,                j                            )                                =                                                    ∑                                  k                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                ∑                                      l                    =                    0                                                        N                    -                    1                                                  ⁢                                                                        E                    ⁡                                          (                                              k                        ,                        l                                            )                                                                                                              =                                          ∑                                  k                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                ∑                                      l                    =                    0                                                        N                    -                    1                                                  ⁢                                                                                              C                      ⁡                                              (                                                                              x                            +                            k                                                    ,                                                      y                            +                            l                                                                          )                                                              -                                          R                      ⁡                                              (                                                                              x                            +                            i                            +                            k                                                    ,                                                      y                            +                            j                            +                            l                                                                          )                                                                                                                                                  ,                            (        1        )            where C is the current image, R is the reference image, and E is the difference macro block (MB) of the current MB and reference MB, (x, y) is the location of current MB, (i,j) is the candidate motion vector, i.e., the location of reference MB, and N is the MB size.
As the technologies of ME and DCT-coding have been adopted to eliminate the temporal and special redundancies in image sequence by most of video compression algorithms, the ME plays a key role for computation complexity, compression efficiency and image quality. Due to the heavy operation load of full search (FS), lots of fast algorithms are developed for real time video coding. Generally, along with reduction of computation complex of ME, the image quality gets poor.
There are several factors which affect image quality. One of the factors is the matching between conventional ME and DCT coding. For example, SAD of luminance pixels has been used as the criterion in ME, due to simplicity and regularity. It generates luminance difference block with globe or local minimum energy, i.e., minimum DC coefficient after DCT, but the DC coefficients might be large and requires bigger encoding bit-amount. In other words, the property of DCT is not taken into account during conventional ME procedure. There might be great special redundancies in the resulted difference block. This causes a poor efficiency of DCT coding.
In the conventional motion estimation, the operation speed, due to much redundant computation in data transformation, is still not sufficiently fast. It should still have some way to improve the operation speed in motion estimation.